package data_structures_and_algorithms.sort.learn;

import javax.naming.ldap.PagedResultsControl;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @ClassName Code02_PartitionAndQuickSort
 * @Description: 快排
 * @Author: yongliang.ma
 * @Create_time:2022/10/27 19:53
 */
public class Code02_PartitionAndQuickSort {

    public static void main(String[] args) {
//        int[] nums = {3,1,5,7,2,1,8,9,6,3,1,6,6};
        int[] nums = { 5, 2,3,1 };
//        split(nums);
//        split2(nums);
        quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 铺垫一：
     * 分割数组为两部分，指定基数为数组最右边数字K，小于等于K得放在数组左边，大于K得放在数组右边
     *
     * 不得使用额外得数组空间
     */
    public static void split(int[] nums){
        if (nums.length < 2)
            return;
        int lessEqual = -1, cur = 0, K = nums[nums.length - 1];
        while (cur < nums.length){
            if (nums[cur] <= K){
                // 这三行代码改进下 简洁一点
//                lessEqual++;
//                swap(nums, lessEqual, cur);
//                cur++;
                swap(nums, ++lessEqual, cur++);
            }else {
                cur++;
            }
        }
    }

    /**
     * 铺垫二：
     * 分割数组为三部分，指定基数为数组最右边数字K，小于K得放在数组左边，等于K得放在中间，大于K得放在数组右边
     *
     * 不得使用额外得数组空间
     */
    public static void split2(int[] nums) {
        if (nums.length < 2)
            return;
        int less = -1, more = nums.length - 1, K = nums[nums.length - 1], cur = 0;
        while (cur < more){
            if (nums[cur] < K){
                swap(nums, ++less, cur++);
            }else if (nums[cur] == K){
                cur++;
            }else {
                // 大于K得情况
                swap(nums, --more, cur);// 因为这里不知道交换回来得数字和K得大小情况，所以需要再次判断下cur位置得情况
            }
        }
        // 将最后一位换到大于K得第一位，也即是more得位置
        swap(nums, more, nums.length - 1);
    }

    /**
     * 组件：分层，以R位置数字K为基准，将小于K得数字放在左边，将等于K得数字放在中间，将大于K得数字放在右边
     *
     * 快排得前奏
     *
     * 返回得数组含义：等于K得数字得范围，从哪个位置到哪个位置
     */
    public static int[] partition(int[] nums, int L, int R){
        // 这里不再判断是否有必要排序，在外层做判断
        int lessR = L - 1, cur = L, moreL = R, K = nums[R];
        while (cur < moreL){
            if (nums[cur] < K){
                swap(nums, ++lessR, cur++);
            }else if (nums[cur] == K){
                cur++;
            }else {
                // 大于K的情况
                swap(nums, --moreL, cur);
            }
        }
        swap(nums, moreL, R);
        // 这里额外注意：lessR + 1原因：起点是第一个等于K的数字，所以需要加一；moreL而不是moreL - 1的原因：moreL位置元素和R位置元素交换过了，所以moreL位置元素等于K，也就是最后一位K值元素
        return new int[]{lessR + 1, moreL};
    }


    public static void quickSort(int[] nums){
        if (nums == null || nums.length < 2)
            return;

        process(nums, 0, nums.length - 1);
    }
    public static void process(int[] nums, int L, int R){
        if (L >= R)
            return;

        int[] partition = partition(nums, L, R);
        // partition[0]：等于区域的第一个数字
        // partition[0]：等于区域的最后一个数字
        process(nums, L, partition[0] - 1);
        process(nums, partition[1] + 1, R);
    }

    public static void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }



    public static void quickSortLoop(int[] nums){
        if (nums == null || nums.length < 2)
            return;
        Deque<Job> deque = new LinkedList<>();
        deque.addFirst(new Job(0, nums.length - 1));
        while (!deque.isEmpty()){
            Job job = deque.removeFirst();
            int[] partition = partition(nums, job.L, job.R);
            // 等同于process中的if条件拦截判断
            if (partition[0] > job.L + 1){// 左侧区间有值才会执行
                deque.addFirst(new Job(job.L, partition[0] - 1));
            }
            if (partition[1] < job.R - 1){// 右侧区间有值才会执行
                deque.addFirst(new Job(partition[1] + 1, job.R));
            }
        }
    }


    public static class Job{
        public Integer L;

        public Integer R;

        public Job(Integer L, Integer R){
            this.L = L;
            this.R = R;
        }
    }












}
